﻿namespace Leetcode.N0239;

public class Solution
{
    public int[] MaxSlidingWindow(int[] nums, int k)
    {
        var queue = new System.Collections.Generic.LinkedList<int>();

        for (var i = 0; i < k; i++)
        {
            while (queue.Count > 0 && nums[i] >= nums[queue.Last.Value])
            {
                queue.RemoveLast();
            }
            queue.AddLast(i);
        }
        var result = new int[nums.Length - k + 1];
        result[0] = nums[queue.First.Value];

        for (var i = k; i < nums.Length; i++)
        {
            while (queue.Count > 0 && nums[i] >= nums[queue.Last.Value])
            {
                queue.RemoveLast();
            }
            queue.AddLast(i);

            if (queue.First.Value < i - k + 1)
            {
                queue.RemoveFirst();
            }
            result[i - k + 1] = nums[queue.First.Value];
        }
        return result;
    }
}
